package review;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode_day4_review {

	/**
	 * When we encounter a '*', the original problem will have 3 possible moves:
	 * 1-	stay in this state
	 * 2-	move to next state
	 * 3-	skip this state
	 * Because we cannot make judgment immediately by making choices
	 * and this will lead to many more subproblems.
	 * 
	 * This is a typical divide and conquer problem.
	 * 
	 * @param str
	 * @param expression
	 * @return
	 */
	public static boolean regularExpressionMatching(String str, String expression){
		if(str == null || expression == null ||(str.length() == 0 && expression.length() != 0)) 
			return false;
		if(str.isEmpty() && expression.isEmpty()) return true;
		char[] cs = str.toCharArray();
		char[] regex = expression.toCharArray();
		
		if(regex.length > 1 && regex[1] == '*'){
			if(regularExpressionMatching(str, expression.substring(2))) return true;// skip this state
			else if(cs[0] == regex[0] || regex[0] == '.'){//2 choices, go to next state, stay in the state
				if(regularExpressionMatching(str.substring(1), expression.substring(2))) return true;//go to next state
				if(regularExpressionMatching(str.substring(1), expression)) return true;//stay in the state
				return false;
			}
		}else{
			if(cs[0] == regex[0] || regex[0] == '.')
				return regularExpressionMatching(str.substring(1), expression.substring(1));
			else return false;
		}		
		return false;
	}
	
	public static String longestCommonPrefix(String[] list){
		//check valid
		if(list == null || list.length == 0) return null;
		if(list.length == 1) return list[0];
		
		//build tire tree
		Node root = new Node('$');
		root.children = new Node[27];
		//for all strings
		for(String temp : list){
			if(temp == null || temp.isEmpty()) continue;
			char[] str = temp.toCharArray();
			Node child;
			//insert the first character
			if(root.children[str[0]-'a'] == null) {
				root.children[str[0]-'a'] = new Node(str[0]);
				root.childNum++;
			}
			
			child = root.children[str[0]-'a'];
			
			//insert other characters
			for(int i = 1 ; i < str.length ; i++){
				
				if(child.children != null){
					if(child.children[str[i]-'a'] == null) {
						child.children[str[i]-'a'] = new Node(str[i]);
						child.childNum++;
					}
				}else{
					child.children = new Node[27];
					child.children[str[i]-'a'] = new Node(str[i]);
					child.childNum++;
				}
				
				child = child.children[str[i]-'a'];
			}
			//At the end of the string, record an end
			//if don't record, "abc","abcs","abc"
			//result will be "abcs"
			if(child.children != null){
				if(child.children[26] == null){
					child.children[26] = new Node('$');
					child.childNum++;
				}
			}else{
				child.children = new Node[27];
				child.children[26] = new Node('$');
				child.childNum++;
			}
		}
		
		//find the longest common prefix
		Node pointer = root;
		StringBuilder sb = new StringBuilder();
		while(pointer.childNum == 1){
			int i;
			for(i = 0 ; i < 26 ; i++)
				if(pointer.children[i] != null) {
					sb.append(pointer.children[i].c);
					break;
				}
			pointer = pointer.children[i];
		}
		
		return sb.toString();
	}
	
	public static List<int[]> threeSum(int[] list, int target){
		if(list == null || list.length < 3) return null;
		Arrays.sort(list);
		List<int[]> result = new ArrayList<int[]>();
		
		//determine the first number
		for(int i = 0 ; i < list.length - 2; i++){
			//find next two numbers
			int tempTarget = target - list[i];
			int left = i+1, right = list.length-1, sum = 0;
			while(left < right){
				sum = list[left] + list[right];
				if(sum >tempTarget) right--;
				else if(sum < tempTarget) left++;
				else{
					int[] res = new int[3];
					res[0] = list[i];
					res[1] = list[left];
					res[2] = list[right];
					result.add(res);
					break;
				}
			}
		}
		
		return result;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		List<int[]> list2 = threeSum(new int[]{-1, 0, 1, 2, -1, -4}, 0);
		System.out.println(regularExpressionMatching("aaab", "c*d*a*aab"));
		String[] list = new String[]{"abc","abcs","abc"};
		System.out.println(longestCommonPrefix(list));
	}
}

class Node{
	public char c;
	public Node[] children = null;
	public int childNum = 0;
	public Node(char c){
		this.c = c;
	}
}
/**
 * Notice:
 * Cannot use a private inner class in static method.
 */
